package ru.ifmo.cppsc.syntactic;

import ru.ifmo.cppsc.grammar.Symbol;
import ru.ifmo.cppsc.grammar.Grammar;
import ru.ifmo.cppsc.grammar.Production;

import java.util.HashSet;
import java.util.Set;

/**
 * Author: Olga Komaleva
 * Date: Jun 15, 2008
 */
public class SyntacticAnalyse {
    protected final Grammar grammar;
    protected final Set<Symbol>[] first;
    public final Symbol STOP_SYMBOL;


    public SyntacticAnalyse(Grammar g) {
        grammar = g;
        STOP_SYMBOL = grammar.addTerminal("$");

        first = new HashSet[g.size()];
        initFirst();

    }

    private void initFirst() {
        for (Symbol symbol: grammar.getSymbols()) {
            first[symbol.getId()] = new HashSet<Symbol>();
            if (grammar.isTerminal(symbol)) {
                first[symbol.getId()].add(symbol);
            }  else {
                if (isReduceableToEpsilon(symbol)) {
                    first[symbol.getId()].add(grammar.EPSILON);
                }
            }
        }

        boolean areChanged = true;
        while (areChanged) {
            areChanged = false;
            for (Symbol symbol: grammar.getSymbols()) {
                 if (!grammar.isTerminal(symbol)) {
                    for (Production p : grammar.getProductions()) {
                        if (p.getRight()[0] != grammar.EPSILON && p.getLeft() == symbol) {
                            areChanged = areChanged || first[symbol.getId()].addAll(first[p.getRight()[0].getId()]);
                        }
                    }
                }
            }
        }
    }

    private boolean isReduceableToEpsilon(Symbol symbol) {
        if (symbol == grammar.getStart()) {
            for (Production p: grammar.getProductions()) {
                if ((p.getLeft() == symbol) && (p.getRight()[0] == grammar.EPSILON)) {
                    return true;
                }
            }
        }
        return false;
    }

    public void printFirst() {
        for (int i = 0; i < first.length; i++) {
            System.out.print(grammar.getSymbolById(i).getName() + ": ");
            for (Symbol s: first[i]) {
                System.out.print(s.getName() + " ");
            }
            System.out.println("");
        }
    }
}
